package com.lishem.carl._10dp;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/combination-sum-iv/
 * <p>
 * 给你一个由不同整数组成的数组nums，和一个目标整数 target。
 * <p>
 * 请你从nums中找出并返回总和为target的元素组合的个数。
 * <p>
 * 示例1：
 * <p>
 * nums = [1,2,3], target = 4  输出：7
 * <p>
 * 所有可能的组合为：
 * <p>
 * (1, 1, 1, 1)
 * <p>
 * (1, 1, 2)
 * <p>
 * (1, 2, 1)
 * <p>
 * (1, 3)
 * <p>
 * (2, 1, 1)
 * <p>
 * (2, 2)
 * <p>
 * (3, 1)
 * <p>
 * 顺序不同的序列被视作不同的组合
 * <p>
 * 示例2：nums = [9], target = 3 输出：0
 */
public class _15LetCode377_组合总和4 {

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        // 求组合，先遍历背包
        for (int i = 0; i <= target; i++) {
            // 再遍历物品
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }


    /**
     * 二维数组版本，不太好理解
     *
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum42(int[] nums, int target) {
        int[][] dp = new int[nums.length + 1][target + 1];
        // 初始化,注意本题是有序的，需要外层遍历背包，内层遍历物品
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        Arrays.sort(nums);
        for (int j = 1; j <= target; j++) { // 行列遍历顺序无所谓，可以颠倒本行和下一行
            for (int i = 1; i <= nums.length; i++) {
                if (j >= nums[i - 1]) {
                    for (int k = 0; k < i; k++) {
                        dp[i][j] += dp[i][j - nums[k]];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[dp.length - 1][target];
    }


    public static void main(String[] args) {
        _15LetCode377_组合总和4 sol = new _15LetCode377_组合总和4();
        int[] nums = {1, 2, 3};
        System.out.println(sol.combinationSum4(nums, 4));
    }
}

